import com.sun.corba.se.impl.orbutil.graph.Graph;

public class Priem {
    public static void main(String[] args) {
        char[]  data={'A','B','C','D','E','F','G'};
        int size=data.length;
        MGraph mGraph = new MGraph(size);
        int[][] wight={
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000},
        };
        MinTree minTree = new MinTree();
        minTree.Graph(size,data,wight,mGraph);
        minTree.showGraph(mGraph,size);
        minTree.Shortestpath(mGraph,1);


    }

}

class MinTree{

    public void Graph(int size,char[] data,int[][] wight,MGraph graph){
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                graph.data[i]=data[i];
                graph.wight[i][j]=wight[i][j];
            }
        }
    }

    public void Shortestpath(MGraph mGraph,int no){


        int[] visited=new int[mGraph.size];
        visited[no]=1;//表示访问过
        int h1=-1;
        int h2=-1;
        int max=10000;//表示这条路不通
        for (int i = 1; i < mGraph.size; i++) {//7个顶点，6条路

            for (int j = 0; j < mGraph.size; j++) {
                for (int k = 0; k < mGraph.size; k++) {
                    if (visited[j]==1&&visited[k]==0&&mGraph.wight[j][k]<max){//j表示访问过的顶点，k表示没有访问过的，小于max表示这条路通
                        max=mGraph.wight[j][k];//获取这条路的距离
                        h1=j;
                        h2=k;
                    }
                }
            }
            System.out.println("<"+mGraph.data[h1]+","+mGraph.data[h2]+">"+max);
            visited[h2]=1;//将顶点设为访问过
            max=10000;
        }

    }
    public void showGraph(MGraph graph,int size){
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                System.out.print(graph.wight[i][j]+" ");
            }
            System.out.println();
        }
    }



}






class MGraph{
    public int size;
    public int[][] wight;
    public char[] data;


    public MGraph(int size) {
        this.size = size;
        data=new char[size];
        wight=new int[size][size];
    }
}